package demo.practice.leetcode;

import java.util.HashMap;
import java.util.Map;

public class P211 {
    private final int ALPHABET_SIZE = 128;
    private Map<Character, P211> children = new HashMap<>();
    boolean isEndOfWord = false;

    /**
     * Initialize your data structure here.
     */
    public P211() {

    }

    /**
     * Adds a word into the data structure.
     */
    public void addWord(String word) {
        P211 current = this;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (current.children.get(c) == null) {
                current.children.put(c, new P211());
            }
            current = current.children.get(c);
        }
        current.isEndOfWord = true;
    }

    /**
     * Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
     */
    public boolean search(String word) {
        return search(this, word, 0);
    }

    public boolean search(P211 node, String word, int i) {
        if(i==word.length()){
            return node.isEndOfWord;
        }
        char c = word.charAt(i);
        if (c != '.') {
            if (node.children.get(c) == null) {
                return false;
            }
            return search(node.children.get(c), word, ++i);
        } else {
            //c=='.'
            ++i;
            for (P211 ch : node.children.values()) {
                if (search(ch, word,i )) {
                    return true;
                }
            }
            return false;
        }
    }

}
